קוד תחיליות (Prefix Codes):

• קידוד המאפשר לייצג תווים נפוצים בעזרת מילות קוד קצרות, ותווים נדירים במילות קוד ארוכות, במטרה לחסוך ביטים (למשל צמצום של מאות אלפי ביטים לקובץ בהשוואה לקידוד 8-ביט רגיל).
• קוד תחיליות הוא קידוד שבו שום מילת קוד אינה תחילית של מילת קוד אחרת. תכונה זו מבטיחה שפענוח (Decoding) יהיה תמיד יחיד.
• ייצוג כעץ:
  • מיוצג בעזרת עץ בינארי. העלים מייצגים את התווים, והמסלול מהשורש לכל עלה מכתיב את מילת הקוד (0 עבור פנייה שמאלה, 1 ימינה).
  • עלות הקוד שווה לסכום מכפלות תדירות התו באורך מסלולו.
• קידוד תחיליות אופטימלי:
  • תמיד קיים קוד תחיליות אופטימלי שבו שני הסמלים הנדירים ביותר נמצאים כעלים אחים באותה רמה (הרמה התחתונה ביותר).
  • ההוכחה מתבססת על החלפת צמתים בעץ האופטימלי וקבלת עלות זהה או טובה יותר.

קוד הופמן (Huffman Code) ומציאת קוד אופטימלי:

• יוצר צומת לכל תו ולתדירות שלו.
• משתמש תור עדיפויות שממיין את הצמתים לפי תדירות. האלגוריתם שולף את שני התווים בעלי התדירות הנמוכה ביותר, מחבר אותם לצומת הורה חדש שתדירותו היא סכום התדירויות של שני בניו, ומכניס את ההורה חזרה לתור.
• זמן הריצה:
  • קיימות $\mathrm{\Theta }(\sigma )$ לולאות (כאשר $\sigma$ כמות התווים השונים בקידוד), ובכל שלב מבצעים חילוץ והכנסה לתור עדיפויות, ולכן זמן הריצה הוא $\mathrm{\Theta }(\sigma \log \sigma )$.
• קוד הופמן בהכרח מוצא עץ אופטימלי.

דחיסת Lempel-Ziv (LZ78):

• מבוסס על איתור חזרות של ביטויים בטקסט במקום הסתמכות על תדירויות תווים.
• מחלק את מחרוזת הקלט לבלוקים, כאשר כל בלוק הוא קידומת מקסימלית של הטקסט שטרם נקרא השווה לבלוק שכבר קודד מקודם, פלוס תו אחד נוסף.
• מקודד כל בלוק כזוג (j,c) כאשר j מציין את המספר הסידורי של בלוק האב, ו-c הוא התו החדש בסוף הבלוק.
• נשמר במבנה של עץ.
• לדוגמא:
  • הרצף a b a b a b c b a b a c יחולק ל: a | b | ab | aba | bc | ba | bac
• פענוח (Decoding):
  • סורק את הבלוקים המקודדים ובונה מחדש את עץ התחיליות.
  • לכל צומת x יש מצביע להורה שלו (x.parent) ואת התו שמפריד ביניהם (x.label).
  • בעזרת מערך של מצביעים לבלוקים, ניתן לשחזר את המחרוזת.
  • זמן הריצה לפענוח הוא $\mathrm{\Theta }(n)$.